package EveryDay;
/**
 * P1870 准时到达列车的最小时速
 * */
public class P1870 {
    public static void main(String[] args) {
        int[] a={1,3,2};
        double hour=1.9;
        P1870Test01 p1870Test01=new P1870Test01();
        System.out.println(p1870Test01.minSpeedOnTime(a, hour));
    }
}


/**
 * 二分答案
 * 利用sum来记录总的时间，比较hour，大的往左边靠（速度慢），小的往右边靠（速度快）
 * */
class P1870Test01 {
    public int minSpeedOnTime(int[] dist, double hour) {
        int l=0,r=1000000009;
        int mid;
        int ans=-1;

        while(l<=r){
            mid=(l+r)/2;
            if(doublySearch(dist, mid, hour)){
                r=mid-1;
                ans=mid;
            }
            else{
                l=mid+1;
            }

        }
        return ans;
    }

    private boolean doublySearch(int[] dist,int mid,double hour){
        double sum=0;
        for(int i=0;i<dist.length;i++){
            double time=(double) dist[i]/mid;
            if(i<dist.length-1){
                sum+=Math.ceil(time);
            }
            else {
                sum+=time;
            }
        }
        //时间少，速度快
        return sum<=hour;
    }

}


